'''
给一个二维列表，表示迷宫（0表示通道，1表示围墙）
给出算法，求出一条走出迷宫的路径
'''

maze = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0 ,1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

dirs = [
    lambda x, y: (x+1, y),  # 下
    lambda x, y: (x-1, y),  # 上
    lambda x, y: (x, y-1),  # 左
    lambda x, y: (x, y+1)   # 右
]

# 栈——深度优先搜索（回溯法）
def maze_path(x1, y1, x2, y2):
    stack = []
    stack.append((x1, y1))
    while(len(stack) > 0):
        curNode = stack[-1]
        if curNode[0] == x2 and curNode[1] == y2:
            for p in stack:
                print(p)
            return True
        # 查找x, y四个方向: x-1, y; x, y-1; x, y+1; x+1, y
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            # 如果下一个节点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2  # 2表示走过了
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()

    else:
        print('没有路')
        return False


# 队列——广度优先搜索
from collections import deque

def print_r(path):
    curNode = path[-1]
    real_path = []

    while curNode[2] != -1:
        real_path.append(curNode[0:2])
        curNode = path[curNode[2]]
    real_path.append(curNode[0:2])
    real_path.reverse()

    for node in real_path:
        print(node)

def maze_path_queue(x1, y1, x2, y2):
    queue = deque()
    queue.append((x1, y1, -1))
    path = []
    while len(queue) > 0:
        curNode = queue.popleft()
        path.append(curNode)
        if curNode[0] == x2 and curNode[1] == y2:
            print_r(path)
        for dir in dirs:
            nextNode = dir(curNode[0], curNode[1])
            if maze[nextNode[0]][nextNode[1]] == 0:
                queue.append((nextNode[0], nextNode[1], len(path) - 1))     # 后续节点进队
                maze[nextNode[0]][nextNode[1]] = 2   
    else:
        print('没有路')
        return False